// 解题思路
// 寻找最近的单元：对于第n阶楼梯，能够到达n的只有是在n-1和n-2的位置。
// 所以 f(n) = f(n-1) + f(n-2)
// f(1)=1
// f(2)=2
// f(3)= f(1)+f(2)

// 解法1： 最朴素的递归方式(执行会超时)
function climbStairs(n:number):number {
    if(n===1){
        return 1;
    }
    if(n===2){
        return 2
    }
    return climbStairs(n-1)+climbStairs(n-2);
}
// 解法2 动态规划
function climbStairs1(n:number):number {
    if(n===1){
        return 1;
    }
    if(n===2){
        return 2
    }
    let f1:number = 1;
    let f2:number = 2;
    let f3:number;
    while(n>2){
        f3 = f1+f2;
        f1 = f2;
        f2 = f3;
        n--;
    }
    return f3;
}

// 解法3 动态规划，数组存储所有的数据
function climbStairs2(n:number):number {
    if(n===1){
        return 1;
    }
    if(n===2){
        return 2
    }
    let nums:number[] = [1,2]
    let start:number = 2
    while(n>start){
        nums[start] = nums[start-1] + nums[start-2];
        start++;
    }
    return nums[n-1];
}
